// https://www.lintcode.com/problem/trapping-rain-water-ii/description

class Solution {
public:
    /**
     * @param heights: a matrix of integers
     * @return: an integer
     */
    int trapRainWater(vector<vector<int>> &heights) {
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, 
            greater<tuple<int, int, int>>> q;
            // priority_queue<pair<int, pair<int, int>>, 
                    //   vector<pair<int, pair<int, int>>>, 
                    //   greater<pair<int, pair<int, int>>>> pq; 这样也可以
        int n = heights.size();
        int m = heights[0].size();
        int res = 0;
        // int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int dir[5] = {0, 1, 0, -1, 0};
        vector<vector<int>> visited(n, vector<int>(m, false));
        for (int i = 0; i < n; ++i) {
            // q.push(make_tuple(heights[i][0], i, 0));
            q.emplace(heights[i][0], i, 0);
            visited[i][0] = true;
            // q.push(make_tuple(heights[i][m - 1], i, m - 1));
            q.emplace(heights[i][m - 1], i, m - 1);
            visited[i][m - 1] = true;
        }
        for (int i = 0; i < m; ++i) {
            // q.push(make_tuple(heights[0][i], 0, i));
            q.emplace(heights[0][i], 0, i);
            visited[0][i] = true;
            // q.push(make_tuple(heights[n - 1][i], n - 1, i));
            q.emplace(heights[n - 1][i], n - 1, i);
            visited[n - 1][i] = true;
        }
        while (!q.empty()) {
            // tuple<int, int, int> tmp = q.top();
            int val, x, y;
            tie(val, x, y) = q.top();
            q.pop();
            // cout << get<1>(tmp) << " " << get<2>(tmp) << endl;
            for (int i = 0; i < 4; ++i) {
                // int nx = get<1>(tmp) + dir[i][0];
                // int ny = get<2>(tmp) + dir[i][1];
                int nx = x + dir[i];
                int ny = y + dir[i + 1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
                    // int nh = max(heights[nx][ny], get<0>(tmp));
                    int nh = max(heights[nx][ny], val);
                    res += nh - heights[nx][ny];
                    // q.push(make_tuple(nh, nx, ny));
                    q.emplace(nh, nx, ny);
                    // visited[nx][ny] == true; //!!!!!!!!!
                    visited[nx][ny] = true;
                }
            }
        }
        return res;
    }
};